4079. Permutation

You are given a permutation of first n positive integers in array. Print the smallest index of array that contains the number in the range from a to b (inclusive).

Input. First line contains two integers n and q (n, q ≤ 10⁵) separated by a space. Second line contains a permutation of n integers (from 1 to n in any order). Then q lines follow: each line contains two integers a and b (a ≤ b ≤ 10⁵) separated by space.

Output.  Print exactly q lines each containing the answer.

Sample input

2 2

2 1

1 2

1 1

Sample output

1

2

SOLUTION

data structures - RMQ

Анализ алгоритма

Пусть массив b содержит входную перестановку. Занесем в ячейку a[i] номер индекса массива b, в котором находится число i. Ответом на запрос (u, v) будет a[RMQ_a[u..v]].

Пример

Рассмотрим входную перестановку в массиве b. Пересчитаем массив a.

Число 1 входной перестановки находится в девятом индексе массива b (b[9] = 1). Следовательно в a[1] занесем 9.

Рассмотрим запрос (a, b) = (2, 4). Число 2 находится в индексе 4, число 3 в индексе 10, число 4 в индексе 7. Рассмотрим содержимое массива а в ячейках 2, 3, 4. Это будут числа 4, 10, 7 – индексы ячеек массива а, в которых находятся числа 2, 3, 4. Остается найти индекс минимального элемента в подмассиве a[2..4]. Он равен 2 (a[2] = 4 = min(4, 10, 7)).

Реализация алгоритма

Объявим массив m, в ячейке m[i][j] которого будем хранить индекс наименьшего элемента на промежутке (i, …, i + 2^j – 1). Объявим дополнительные массивы a и b.

#define DIM1 100010

#define DIM2 17

int m[DIM1][DIM2];

int a[DIM1], b[DIM1];

Читаем входные данные. Заносим перестановку в массив b.

scanf("%d %d",&n,&q);

for(i = 1; i <= n; i++) scanf("%d",&b[i]);

Пересчитаем данные массива a.

for(i = 1; i <= n; i++) a[b[i]] = i;

Произведем предобработку данных для запросов RMQ.

rmq();

Читаем запрос (u, v) и выводим на него ответ.

for(i = 0; i < q; i++)

{

scanf("%d %d",&u,&v);

printf("%d\n",a[Query(u,v)]);

}